package cn.edu.thu.tsquality.core.algorithm.sequential.dependencies;


import javafx.util.Pair;

public class SegmentTree
{
    private class Node
    {
        private Node lson;
        private Node rson;
        private Treap treap;

        Node()
        {
            lson = rson = null;
            treap = new Treap();
        }

        Node(Node lson, Node rson, Treap treap)
        {
            this.lson = lson;
            this.rson = rson;
            this.treap = treap;
        }


    }


    private int inputSize;
    private Node root;
    private static final int infInt = 0x3f3f3f3f;

    SegmentTree(int inputSize)
    {
        this.inputSize = inputSize;
        root = build(1,inputSize);
    }

    private Node build(int l, int r)
    {
        if(l == r)
            return new Node();
        int mid = (l + r) / 2;
        return new Node(build(l, mid), build(mid+1, r), new Treap());
    }

    private Pair<Integer, Integer> query(Node node, int l, int r, int queryOuterL, int queryOuterR, int queryInnerL, int queryInnerR)
    {
        if(l >= queryOuterL && r <= queryOuterR)
            return node.treap.query(queryInnerL, queryInnerR);
        int mid = (l + r) / 2;
        int minValue = infInt;
        int minValueRealPosition = -1;

        if(queryOuterL <= mid)
        {
            Pair<Integer, Integer> lson = query(node.lson, l, mid, queryOuterL, queryOuterR, queryInnerL, queryInnerR);
            if (lson.getKey() < minValue)
            {
                minValue = lson.getKey();
                minValueRealPosition = lson.getValue();
            }
        }

        if(queryOuterR > mid)
        {
            Pair<Integer, Integer> rson = query(node.rson, mid + 1, r, queryOuterL, queryOuterR, queryInnerL, queryInnerR);
            if (rson.getKey() < minValue)
            {
                minValue = rson.getKey();
                minValueRealPosition = rson.getValue();
            }
        }
        return new Pair<>(minValue, minValueRealPosition);
    }

    public Pair<Integer, Integer> query(int queryOuterL, int queryOuterR, int queryInnerL, int queryInnerR)
    {
        return query(root, 1, inputSize, queryOuterL, queryOuterR, queryInnerL, queryInnerR);
    }

    private Node insert(Node node, int l, int r, int outerPosition, int innerPosition, int value, int realPosition)
    {
        if(l == r)
        {
            node.treap.insert(innerPosition, value, realPosition);
            return new Node(null, null, node.treap);
        }

        int mid = (l + r) / 2;
        if(outerPosition <= mid)
        {
            node.treap.insert(innerPosition, value, realPosition);
            return new Node(insert(node.lson, l, mid, outerPosition, innerPosition, value, realPosition), node.rson, node.treap);
        }
        else
        {
            node.treap.insert(innerPosition, value, realPosition);
            return new Node(node.lson, insert(node.rson, mid + 1, r, outerPosition, innerPosition, value, realPosition), node.treap);
        }

    }

    public void insert(int outerPosition, int innerPosition, int value, int realPosition)
    {
        root = insert(root, 1, inputSize, outerPosition, innerPosition, value, realPosition);
    }

}
